using System;
using System.Collections.Generic;

namespace JapaneseLearning.Tools
{
    internal class PrimeModRandom
    {
        /// <summary>
        /// 循环求随机数的次数
        /// </summary>
        private int _randomCount = 0;

        private int _p;
        private int _m;
        private Random _random;
        private readonly int _max;
        private readonly int[] _randomPrimes;

        public PrimeModRandom(int max)
        {
            if (max < 2)
                throw new Exception("params error");
            _max = max;
            _randomCount = max;
            _randomPrimes = OptimizedPrimeSieve(max - 1).ToArray();
        }

        public int Next()
        {
            if (_randomCount == _max)
            {
                _random = new Random(DateTimeTools.GetTimeStamp());
                _randomCount = 0;
                var i = _random.Next();
                _m = i % _max;
                _p = _randomPrimes[i % _randomPrimes.Length];
            }

            var result = (_m + _p) % _max;
            _m = result;
            _randomCount++;
            return result;
        }

        /// <summary>
        /// 1 到最大数中的素数
        /// </summary>
        private List<int> OptimizedPrimeSieve(int max)
        {
            if (max < 2) return new List<int>();
            var primes = new List<int> { 2 }; // 预添加2

            if (max == 2) return primes;

            // 只处理奇数（内存减半）
            var sieveSize = (max - 1) >> 1; // 等价于(max-1)/2
            var arraySize = (sieveSize + 31) >> 5; // 转换为uint数组大小
            var sieve = new uint[arraySize];

            // 初始化所有位为1（表示素数）
            //Array.Fill(sieve, 0xFFFFFFFFU); // .NET 5+特性
            for (var i = 0; i < sieve.Length; i++)
            {
                sieve[i] = 0xFFFFFFFFU;
            }

            var upperBound = (int)Math.Sqrt(max);
            for (var i = 0;; i++)
            {
                var p = (i << 1) + 3; // 还原实际数值：3,5,7...
                if (p > upperBound) break;

                // 检查当前位是否为素数
                if ((sieve[i >> 5] & (1U << (i & 31))) != 0)
                {
                    // 标记从p²开始的奇数倍（步长2p）
                    var start = (p * p - 3) >> 1; // 转换为索引
                    for (var j = start; j < sieveSize; j += p)
                    {
                        sieve[j >> 5] &= ~(1U << (j & 31)); // 位操作清除非素数
                    }
                }
            }

            // 收集所有素数（位遍历比LINQ快10倍）
            for (var i = 0; i < sieveSize; i++)
            {
                if ((sieve[i >> 5] & (1U << (i & 31))) != 0)
                    primes.Add((i << 1) + 3);
            }

            return primes;
        }
    }
}